#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, mod = 1000000009;
int a[N];
int n, k, cnt1, cnt2;

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    int l = 0, r = n - 1, flag = 1;

    int res = 1;
    if (k % 2)
    {
        res = a[r--];
        k--;
        if (res < 0)
            flag = -1;
    }

    while (k)
    {
        LL x = (LL)a[l] * a[l + 1], y = (LL)a[r] * a[r - 1];
        if (x * flag > y * flag)
        {
            res = x % mod * res % mod;
            l += 2;
        }
        else
        {
            res = y % mod * res % mod;
            r -= 2;
        }
        k -= 2;
    }
    cout << res << endl;
    return 0;
}